package top100

import "sort"

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		var left = i + 1
		var right = len(nums) - 1
		var target = -nums[i]
		for left < right {
			var sum = nums[left] + nums[right]
			if sum == target {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				var leftVal = nums[left]
				for left < right && nums[left] == leftVal {
					left++
				}
				var rightVal = nums[right]
				for left < right && nums[right] == rightVal {
					right--
				}
			} else if sum < target {
				left++
			} else {
				right--
			}
		}
	}
	return res
}

func trap(height []int) int {
	var postMax = make([]int, len(height)+1)
	for i := len(height) - 1; i >= 0; i-- {
		if height[i] > postMax[i+1] {
			postMax[i] = height[i]
		} else {
			postMax[i] = postMax[i+1]
		}
	}
	var sum = 0
	var preMax = 0
	for i := 0; i < len(height); i++ {
		var min = getMin(preMax, postMax[i]) - height[i]
		if min > 0 {
			sum += min
		}
		if height[i] > preMax {
			preMax = height[i]
		}

	}
	return sum
}
func findAnagrams(s string, p string) []int {
	if len(s) < len(p) {
		return []int{}
	}
	var winMap = [26]int{}
	for i := 0; i < len(p); i++ {
		winMap[p[i]-'a']++
	}
	var left = 0
	var right = 0
	var curWinMap = [26]int{}
	for right < len(p) {
		curWinMap[s[right]-'a']++
		right++
	}

	var res []int
	for right < len(s) {
		if curWinMap == winMap {
			res = append(res, left)
		}
		curWinMap[s[left]-'a']--
		left++
		curWinMap[s[right]-'a']++
		right++
	}
	if curWinMap == winMap {
		res = append(res, left)
	}
	return res
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var fast = head.Next
	var slow = head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	var rightHead = slow.Next
	slow.Next = nil
	var sortRightHead = sortList(rightHead)
	var sortLeftHead = sortList(head)
	var virtualHead = &ListNode{}
	var pre = virtualHead
	for sortLeftHead != nil || sortRightHead != nil {
		if sortLeftHead != nil && sortRightHead != nil {
			if sortLeftHead.Val < sortRightHead.Val {
				pre.Next = sortLeftHead
				sortLeftHead = sortLeftHead.Next
			} else {
				pre.Next = sortRightHead
				sortRightHead = sortRightHead.Next
			}
			pre = pre.Next
			pre.Next = nil
		} else if sortLeftHead != nil {
			pre.Next = sortLeftHead
			break
		} else {
			pre.Next = sortRightHead
			break
		}
	}
	return virtualHead.Next
}
